package org.aplombh.java.leetcode.all;

import java.util.Arrays;

public class _16最近接近的三数之和 {
    public static void main(String[] args) {
        System.out.println(new Solution16_2().threeSumClosest(new int[]{2,3,8,9,10}, 16));
    }
}

// 双指针
class Solution16_2 {
    public int threeSumClosest(int[] nums, int target) {

        int n = nums.length;
        Arrays.sort(nums);

        int ans = Integer.MAX_VALUE;

        for (int i = 0, j, k; i < n; i++) {

            if (n - i <= 2)
                break;

            // 从第二个开始去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int first = nums[i];
            int target1 = target - first;

            // 目标 从j 到k 找到两个相加值等于target的两个值
            for (j = i + 1, k = n - 1; j < k; ) {

                // 从第二个开始去重
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    j++;
                    continue;
                }

                if (k < n - 1 && nums[k] == nums[k + 1]) {
                    k--;
                    continue;
                }


                int second = nums[j];
                int third = nums[k];

                // 比较ans和当前值谁和target比较接近
                int d1 = Math.abs(target - ans);
                int d2 = Math.abs(target - (first + second + third));
                if (d2 < d1)
                    ans = first + second + third;

                if (second + third == target1) {
                    return target;
                } else if (second + third < target1) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return ans;
    }
}

